
/***********
 * EECE 476
 *  Johnathan Chu
 *	Kris Mazurek
 */

#include "stdio.h"
#include "string.h"
#include <assert.h>
#include <stdlib.h>

#include "trace.h"

#define DEBUG 1

// Structures to define cache organization
int num_instrs;
typedef struct block_ {
	int m_valid;
	int m_dirty;	// Represents dirty bit
	unsigned m_tag;
} block;

typedef struct cache_ {
	block* m_tag_array;
	unsigned m_total_blocks;
	unsigned m_set_shift;
	unsigned m_set_mask;
	unsigned m_tag_shift;
	unsigned m_accesses;
	unsigned m_misses;
	unsigned m_nways;
	unsigned m_timestamp;
} cache;

int isHit( cache *c, unsigned index, unsigned tag )
{
	unsigned i;
	
		c->m_tag_array[index].m_timestamp = num_instrs;
		if( c->m_tag_array[index].m_valid && tag == c->m_tag_array[index].m_tag )
		{
			//c->m_tag_array[(c->m_nways * index)].m_timestamp = num_instrs;
			return 1; 
		}	
	}
	
	return 0;
}

void cache_access( cache *c, unsigned addr )
{
	unsigned index, tag;
	index = (addr >> c->m_set_shift) & c->m_set_mask;
	tag = (addr >> c->m_tag_shift);
	assert( index < c->m_total_blocks );
	c->m_accesses++;

	for(i = 0; i < c->m_nways; i++){
		if( !isHit( c, index, tag ) )
		{
			c->m_misses++;
			c->m_tag_array[index].m_valid = 1;
			c->m_tag_array[index].m_tag = tag;
			
		}
	}
}

unsigned LOG2( unsigned n )
{
	unsigned i = 0;
	while( (1 << i) < n )
		++i;
	
	return i;
}

cache *make_cache( char *type, unsigned num_blocks, unsigned block_size_bytes, unsigned m_nways )
{
	cache *this_cache = (cache *)calloc( sizeof(cache), 1 );
	
	// Divide the num_blocks by m_nways because if we increase associativity, we decrease the number of indexes by a corresponding value
	unsigned num_index_bits = LOG2( num_blocks );
	
	//Because in n_ways set associated cache the # of bytes per index will be m_nways times, multiply the block_size_bytes by m_nways before taking LOG2.
	unsigned num_offset_bits = LOG2( block_size_bytes /* m_nways*/ );
	
	this_cache->m_total_blocks = num_blocks;

	this_cache -> m_tag_array = (block *)calloc( sizeof(block), num_blocks) ;
	//this_cache->m_tag_array = (block *)calloc( sizeof(block), m_nways) ); //changing num_blocks in the second argument to m_nways. from what I understand m_tag_array is the size pf each set of blocks
	this_cache->m_set_mask = num_blocks - 1;
	this_cache->m_set_shift = num_offset_bits;
	this_cache->m_tag_shift = num_index_bits + num_offset_bits;
	this_cache->m_accesses = 0;
	this_cache->m_misses = 0;
	this_cache->m_nways = m_nways;
	
	printf( "new %s-cache: %0.1fKB, %d blocks, %d bytes/block, %d -set associative\n", type, 1.0 * num_blocks * block_size_bytes / 1024, num_blocks, block_size_bytes, m_nways );
	
	return this_cache;
}



int main(int argc, char* argv[])
{

	// declare statistics variables here
	int num_memory_accesses = 0;
	num_instrs = 0;
	int num_data_load_accesses = 0;
	int num_data_store_accesses = 0;

#if DEBUG
	printf(" This is a debug test \n");
#endif
	// declare and initialize caches here
	cache *icache = make_cache( "i", 512, 64, 2 );
	cache *dcache = make_cache( "d", 512, 64, 2 );

	// open the trace file
	char trace_filename[MAX_STR];
	if (argc > 1) {
		sscanf(argv[1], "%s", trace_filename);
	} else {
		printf("Usage: %s <trace_file>\n", argv[0]);
		return 1;
	}

	initInstructionStream( trace_filename );
	instruction current_instruction;
	while( getNextInstruction( &current_instruction ) ) {

		// Count instructions and memory accesses here
		++num_instrs;
		++num_memory_accesses;
		
		// Is this a data memory (load or store) instruction?
		if( isLoad(current_instruction.op) )
		{
			++num_memory_accesses;
			++num_data_load_accesses;
		}
		else if( isStore(current_instruction.op) )
		{
			++num_memory_accesses;
			++num_data_store_accesses;
		}
		
		cache_access( icache, current_instruction.pc );
	}
	closeInstructionStream();

	// OFFICIAL PRINT STATEMENTS FOR AUTO-MARKING
	// DO NOT PRINT ANYTHING ELSE BEFORE THESE LINES!!
	// DO NOT REMOVE THESE LINES!!!
	printAccesses( num_memory_accesses, num_instrs,
		num_data_load_accesses, num_data_store_accesses );
	printCacheRates( "i", num_instrs, icache->m_misses, icache->m_accesses );
	printCacheRates( "d", num_instrs, dcache->m_misses, dcache->m_accesses );

	// Print your own information and statistics after this line
	printf( "I-cache miss rate = %0.4f%%\n", 100.0 * icache->m_misses / icache->m_accesses );
	printf( "I-cache MKPI = %0.4f\n", 1000.0 * icache->m_misses / num_instrs );
}
